1. Field of the Invention
This invention relates to methods of intrusion detection in a computer system, and more particularly, to cost-sensitive machine learning techniques that can construct detection models optimized for cost considerations.
2. Background Information
Given the increasing reliance by businesses, governmental bodies, educational institutions, and individuals upon network-based computer systems, it has become critical to protect these systems from “intrusions” or “attacks” (such terms used interchangeably herein), which are typically unauthorized and/or malicious activity. These intrusions may have the effect of compromising security, corrupting data or erroneous output, or causing complete or partial shutdowns of such computer systems. Consequently, intrusion detection, the process of identifying and responding to malicious activity targeted at computing and networking resources, has become a critical component of computer system infrastructure protection mechanisms.
A primary focus of existing intrusion detection development to date is an attempt to maximize the detection accuracy and bandwidth capabilities of an Intrusion Detection System (“IDS”). Consequently, many existing IDS developers have used “brute force” techniques to attempt to correctly detect a larger spectrum of intrusions than their competitors, e.g., a higher percentage of “true positive” detections, while having lower percentages of “false negative” (e.g., intrusions misclassified as normal activity) and “false positives” or false alarms (e.g., normal activity misclassified as an intrusion). However, the goal of catching all intrusions has proven to be a major technical challenge. After more than two decades of research and development efforts, many known IDS's have marginal detection rates and high false alarm rates, especially when detecting stealthy or novel intrusions.
Exemplary, novel techniques for intrusion detection are described in co-pending U.S. application Ser. No. 10/208,402 filed Jul. 30, 2002, entitled “System and Methods For Intrusion Detection With Dynamic Window Sizes,” U.S. application Ser. No. 10/208,432 filed Jul. 30, 2002, entitled “System and Methods For Detection of New Malicious Executables,” and U.S. application Ser. No. 10/222,632 filed Aug. 16, 2002, entitled “System and Methods For Detecting Malicious Email Transmission,” each of which is incorporated by reference in its entirety herein.
The above-stated goal of attempting to catch all intrusions encounters several impracticalities in IDS deployment, such as constraints on time (e.g., processing speed) and availability of resources (both human and computer). These constraints may become overwhelmingly restrictive to the operation of an IDS. An IDS usually perform passive monitoring of a network or system activities, e.g., observing the traffic on a network or system without any attempt to control access to or from that network or system, rather than active filtering, e.g., “in-line monitoring,” which typically occurs on a host that spans multiple networks and can filter traffic to and/or from any of those networks (as is the case with Firewalls). It is desirable for an IDS to keep up with the throughput of the data stream that it monitors, i.e., handle the high bandwidths of the data stream being monitored in real time, so that intrusions can be detected in a timely manner. A real-time IDS can thus become vulnerable to overload intrusions, such as those described in T. Ptacek and T. Newsham, “Insertion, Evasion and Denial of Service: Eluding Network Intrusion Detection,” Secure Networks, Inc., January 1998, online publication http:/www.merit.edu/merit/resources/idspaper.html, which is incorporated by reference in its entirety herein. In an overload intrusion, the intruder first directs a huge amount of malicious traffic at the IDS (or some machine being monitored by the IDS) and devotes resources to this malicious traffic to the point that it can no longer track all data necessary to detect every intrusion. With the diversion of the IDS resources, the intruder can then successfully execute a subsequent, intended intrusion, which the IDS will be unable to detect. Similarly, an incident response team may be overloaded by intrusion reports and may decide to raise detection and response thresholds, as described in R. P. Campbell and G. A. Sands, “A Modular Approach to Computer Security Risk Management,” AFIPS Conference Proceedings, AFIPS Press, 1979. As a consequence of raising the detection and response thresholds, real intrusions may be ignored.
Some study has been performed to categorize intrusions from different perspectives, although there is no established taxonomy in general use. For example, Lindqvist and Jonsson introduced the concept of the classifying an intrusion by “dimension.” (Further details are provided in Ulf Lindqvist et al., “How to Systematically Classify Computer Security Intrusions,” Proceedings of the 1997 IEEE Symposium on Research in Security and Privacy, Oakland, Calif., May 1997, pp. 154-163, which is incorporated by reference in its entirety herein.) The “intrusion results” dimension categorizes intrusions according to their effects (e.g., whether or not denial-of-service is accomplished). The “intrusion techniques” dimension categorizes intrusions based on their methods (e.g., resource or bandwidth consumption). The “intrusion target” dimension categorizes intrusions according to the resource being targeted.
Credit card fraud detection and cellular phone fraud detection also deal with detecting abnormal behavior. Both of these applications are motivated by cost-saving and therefore use cost-sensitive modeling techniques. In credit card fraud detection, for example, the cost factors include operation cost, the personnel cost of investigating a potentially fraudulent transaction (referred to as challenge cost), and loss (referred to as damage cost). If the Dollar amount of a suspected transaction is lower than the challenge cost, the transaction is authorized and the credit card company will take the potential loss. Since the cost factors in fraud detection can be folded into dollar amounts, the cost-sensitive analysis and modeling tasks are much more simple than in intrusion detection.
A disadvantage of current IDS's is that no organized analysis of the costs attributable to intrusion detection and the costs attributable to the intrusion itself is performed to determine how or whether to respond to each intrusion. Currently these cost factors are, for the most part, ignored as unwanted complexities in the development process of an IDS. Some current IDSs try to minimize operational cost, as merely one cost factor among many relevant cost factors. For example, the Bro scripting language for specifying intrusion detection rules does not support for-loops because iteration through a large number of connections is considered time consuming. (See, Paxson, “Bro: A System for Detecting Network Intruders in Real-Time,” Proceedings of the 7th USENIX Security Symposium, San Antonio, Tex., 1998.)
Glaseman et al. discussed a model for evaluating the total expected cost in using a security system s as C(s)=O(s)+D(s), where O(s) is the operational cost of s and D(s) is the expected loss. (As discussed in S. Glaseman, R. Turn, and R. S. Gaines. “Problem Areas in Computer Security Assessment,” Proceedings of the National Computer Conference, 1977.) D(s) is calculated by summing the products of exposed value and the probability of safeguard failure over all possible threats.
However, such existing art do not evaluate the cost-effectiveness of the intrusion detection or perform a cost-benefit tradeoff, which may include development cost, the cost of damage caused by an intrusion, the cost of manual or automatic response to an intrusion, and the operational cost, which measures constraints on time and computing resources. Glaseman et al. do not define consequential cost to include the response cost and model its relationship with damage cost, and does not allow cost-based optimization strategies to be explored. For example, Glasemen et al. does not teach that an intrusion which has a higher response cost than damage cost should usually not be acted upon beyond simple logging.
Accordingly, there is a need in the art to provide a technique to evaluating the cost-effectiveness, or to perform a cost-benefit trade-off in the detection and response to individual intrusions, and to construct detection models optimized for overall cost metrics instead of only statistical accuracy.